You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.
The lock initially starts at '0000', a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
Input: deadends = ["8888"], target = "0009" Output: 1 Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Explanation: We can't reach the target without getting stuck.
Example 4:
Input: deadends = ["0000"], target = "8888" Output: -1
Constraints:
1 <= deadends.length <= 500deadends[i].length == 4target.length == 4- target will not be in the list
deadends. targetanddeadends[i]consist of digits only.
Average Rating: 4.16 (57 votes)
Approach #1: Breadth-First Search [Accepted]
Intuition
We can think of this problem as a shortest path problem on a graph: there are 10000 nodes (strings '0000' to '9999'), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so '0' and '9' differ by 1), and if both nodes are not in deadends.
Algorithm
To solve a shortest path problem, we use a breadth-first search. The basic structure uses a Queue queue plus a Set seen that records if a node has ever been enqueued. This pushes all the work to the neighbors function - in our Python implementation, all the code after while queue: is template code, except for if node in dead: continue.
As for the neighbors function, for each position in the lock i = 0, 1, 2, 3, for each of the turns d = -1, 1, we determine the value of the lock after the i-th wheel has been turned in the direction d.
Care should be taken in our algorithm, as the graph does not have an edge unless both nodes are not in deadends. If our neighbors function checks only the target for being in deadends, we also need to check whether '0000' is in deadends at the beginning. In our implementation, we check at the visitor level so as to neatly handle this problem in all cases.
In Java, our implementation also inlines the neighbors function for convenience, and uses null inputs in the queue to represent a layer change. When the layer changes, we depth++ our global counter, and queue.peek() != null checks if there are still nodes enqueued.
Complexity Analysis
-
Time Complexity: O(N2∗AN+D) where A is the number of digits in our alphabet, N is the number of digits in the lock, and D is the size of
deadends. We might visit every lock combination, plus we need to instantiate our setdead. When we visit every lock combination, we spend O(N2) time enumerating through and constructing each node. -
Space Complexity: O(AN+D), for the
queueand the setdead.
Last Edit: November 14, 2019 4:37 AM
Complexity: O(N^2 * A^N + D)
where, N is Number of dials (4 in our case)
A is number of alphabets (10 in our case -> 0 to 9)
D is the size of deadends.
There are 10 x 10 x 10 x 10 possible combinations => 10^4 => A^N
For each combination, we are looping 4 times (which is N) and in each iteration, there are substring operations ( which is O(N) * constant) => O(4N*constant) => O(4N) => O(NN) => O(N^2)
Total complexity => A^N * N^2, plus D to create the hashset => N^2 * A^N + D
Last Edit: March 29, 2019 12:18 PM
Yeah, where N is the length of lock (4 in our case):
- O(N) for enumerating neighbors,
- O(digits^N) (10^4 in this case neighbors for each node)
- O(D) for initializing deadends set
So time complexity is O(N*digits^N + D)
December 4, 2018 3:20 PM
The time for enumerating the neighbors of each node is O(2N) which is O(N) not O(N^2). Just go through each digit with exploring digit+1 and digit-1.
dead and seen can be united as one set actually for simplicity.
Given the search space it would be better if we did double sided BFS -- layer by layer BFS from "0000" and the target.
Last Edit: February 26, 2020 12:12 AM
I guess I seem to feel some sort of disarmed with problems that require thinking "oh, here I will just do 10000 combinations for the number of 4 elements"...
Inserting null as a delimiter between layers is smart approach and allows to avoid storing depth for each element of the queue. However, as Queue JavaDoc states, "Even in the implementations that permit it, null should not be inserted into a Queue".
March 11, 2020 8:56 PM
Problems like these are good candidates for A* search rather than BFS since you can easily calculate the admissible heuristic as the Manhattan distance to the target.
June 4, 2019 11:41 AM
for the time complexity, where does the N^2 come from?
May 9, 2019 10:15 PM
This solution is actually slow (runs in 126ms in my trial). Instead of a breadth-first search, it is much better to use a directed approach like A*. You can check out my 23ms solution here: https://leetcode.com/problems/open-the-lock/discuss/289516/My-23ms-A*-Java-solution-using-a-priority-queue-(beats-96)
xxxxxxxxxxclass Solution {public: int openLock(vector<string>& deadends, string target) { set<string> deads(deadends.begin(), deadends.end()); queue<string> q; set<string> visit; q.push("0000"); int step = 0; while(!q.empty()) { int size = q.size(); for(int i=size-1;i>=0;i--) { string s = q.front(); q.pop(); if(deads.count(s) || visit.count(s)) continue; if(s==target) return step; visit.insert(s); for(int i=0;i<4;i++) { string next_up = s; next_up[i] = s[i] == '9' ? '0' : s[i]+1; q.push(next_up); string next_down = s; next_down[i] = s[i] == '0' ? '9' : s[i]-1; q.push(next_down); } } step++; } return -1; }};